# 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
# 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。
# 换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
# 0 <= j <= nums[i]
# i + j < n
# 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。


def jumpgame2(nums):
    n = len(nums)
    maxnum = 0
    if n == 1:
        return maxnum
    for i in range(n):
        if i <= maxnum:
            maxnum = max(maxnum,i+nums[i])
            if maxnum >= n-1:
                return i+1



# nums = [2,3,1,1,4]
# nums2 = [2,3,1,0,4]
nums3 = [1,2,1,1,1]
# print(jumpgame2(nums))
# print(jumpgame2(nums2))
print(jumpgame2(nums3))